/*
https://leetcode.cn/problems/count-complete-tree-nodes/description/
222. 完全二叉树的节点个数
medium, 彭珵 2024.09.13
二分查找
*/


class Solution {
public:
    // 计算完全二叉树中节点的数量
    int countNodes(TreeNode* root) {
        TreeNode* cur = root; // 从根节点开始
        int level = 1; // 初始化当前层级（从1开始）
        int h = getDepth(root); // 获取树的高度
        int numbers = 0; // 用于存储节点总数的变量

        // 遍历树以计算节点数量
        while (cur) {
            TreeNode* temp = cur->right; // 检查右子节点
            // 如果右子树的深度与预期高度匹配
            if (level + getDepth(temp) == h && temp) {
                cur = cur->right; // 移动到右子节点
                numbers += pow(2, h - level - 1); // 加上左子树中的节点数量
                level += 1; // 增加层级
            } else {
                cur = cur->left; // 移动到左子节点
                level += 1; // 增加层级
            }
        }

        // 添加最后一层（完整左子树）中计数的节点
        return numbers + pow(2, h - 1);
    }

    // 辅助函数计算二叉树的深度
    int getDepth(TreeNode* root) {
        int depth = 0; // 初始化深度计数器
        while (root) {
            root = root->left; // 向下遍历到最左侧的节点
            depth++; // 每经过一个左节点，深度加一
        }
        return depth; // 返回找到的总深度
    }
};